// 约瑟夫问题
// n个人围成一圈，从约定编号为K(1<=k<=n)的人开始报数，第m个将被杀掉，依次类推，最后剩下一个，其余人都将被杀掉。

// 表示一个节点
class Boy {
    #no = -1
    #next = null

    constructor (no) {
        this.#no = no
    }

    get no () {
        return this.#no
    }

    set no (value) {
        this.#no = value
    }

    get next () {
        return this.#next
    }

    set next (value) {
        this.#next = value
    }
}

// 环形链表
class CircleSingleLinkedList {
    #first = new Boy(-1)

    /**
     *
     * @param nums {number}
     */
    addBoy (nums) {
        if (nums < 1) {
            console.log('不能小于1')
            return
        }
        let curBoy = null
        for (let i = 1; i <= nums; i++) {
            let boy = new Boy(i)
            if (i === 1) {
                this.#first = boy
                this.#first.next = this.#first
                curBoy = this.#first
            } else {
                curBoy.next = boy
                boy.next = this.#first
                curBoy = boy
            }
        }
    }

    showBoy () {
        if (this.#first.next === null) {
            console.log('链表为空')
            return
        }
        let curBoy = this.#first
        while (true) {
            console.log('Boy:', curBoy.no)
            if (curBoy.next === this.#first) {
                break
            }
            curBoy = curBoy.next
        }
    }

    /**
     *
     * @param k {number} 从哪里开始数数
     * @param m {number} 数几下
     * @param n {number} 最初有多少人
     */
    countBoy (k, m, n) {
        if (this.#first === null || k < 1 || k > n) {
            console.log('参数不科学，请重试')
            return
        }
        let helper = this.#first
        // 先让辅助指针指向最后一个节点
        while (true) {
            if (helper.next === this.#first) { // 说明指向最后一个节点
                break
            }
            helper = helper.next
        }
        // 报数前 先让first和helper移动k -1 次
        for (let i = 0; i < k - 1; i++) {
            this.#first = this.#first.next
            helper = helper.next
        }
        // 开始报数 让first和helper指针同时移动m-1次
        while (true) {
            if (helper === this.#first) { // 说明圈中只有一个节点
                break
            }
            for (let i = 0; i < m - 1; i++) {
                this.#first = this.#first.next
                helper = helper.next
            }
            console.log(this.#first.no)
            this.#first = this.#first.next
            helper.next = this.#first
        }
        console.log('最后一个：', helper.no)
    }
}

function test () {
    console.log('测试-单向环形链表')
    let circleSingleLinkedList = new CircleSingleLinkedList()
    circleSingleLinkedList.addBoy(5)
    circleSingleLinkedList.showBoy()

    console.log('测试-约瑟夫问题')
    circleSingleLinkedList.countBoy(1, 2, 5) // 2->4->1->5->3
}

test()
